
//不带头双链表

import java.util.List;

public class MyLinkedList {

    //节点
      static class ListNode{

        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val){
            this.val = val;
        }
    }

    //头和尾
      public ListNode head;
      public ListNode last;

      //计算长度
    public int count;

      //头插法
    public void addFirst(int data) {
        ListNode Node = new ListNode(data);
        //首次增加
        if (head == null) {
            head = Node;
            last = Node;
        }
        //已存在元素增加
        else {
            head = Node;
            head.next = last;
            last.prev = head;
        }
        this.count++;
    }

        //尾插法
        public void addLast(int data){
            ListNode Node = new ListNode(data);
            //首次插入
            if(head == null){
                head = Node;
                last = Node;
            }else{
               last.next = Node;
               Node.prev = last;
               last = Node;

            }
            this.count++;
    }

    private boolean weatherPosLegal(int pos){
        if(pos < 0 || pos > count){
            return true;
        }else return false;
    }

    //指定位置插入
    public void addPos(int index,int data){
        //判断位置是否合法
        if(weatherPosLegal(index))
            throw new PosExption("位置非法...");
        //头插法
        if(index == 0){
            addFirst(data);
            return;
        }
        //尾插法
        if(index == size()){
            addLast(data);
            return;
        }

        ListNode cur = search(index);

        ListNode node = new ListNode(data);

        //中间插入
        cur.prev.next = node;
        node.prev = cur.prev;
        node.next = cur;
        cur.prev = node;

        this.count++;

    }
    private ListNode search(int index){
        ListNode tem = head;
        while(index > 0){
            tem = tem.next;
            index--;
        }
        return tem;
    }
//    public void addPos(int pos,int data){
//        //判断位置是否合法
//        if(weatherPosLegal(pos))
//            throw new PosExption("位置非法...");
//
//        ListNode Node = new ListNode(data);
//
//        //找到插入位置的前一个节点
//        ListNode tem = head;
//
//        //头插
//        if(pos == 0){
//            tem.prev = Node;
//            Node.next =tem;
//            head = Node;
//            this.count++;
//            return;
//        }
//
//        while(pos > 1){
//            tem = tem.next;
//            pos--;
//        }
//        //尾插
//        if(tem.next == null){
//            Node.prev = tem;
//            tem.next = Node;
//            last = Node;
//        }else{
//        //中间插
//        tem.next.prev = Node;
//        Node.next = tem.next;
//        Node.prev = tem;
//        tem.next = Node;}
//
//        this.count++;
//    }

    //统计长度
    public int size(){
        int cnt = 0;
        ListNode tem = head;
        while(tem != null){
            cnt++;
            tem = tem.next;
        }
        return cnt;
    }

//删除首次出现的元素
    public void remove(int key){

        ListNode tem = head;

        while(tem != null){
            if(tem.val == key){
                if(tem == head){
                   head = head.next;
                   if(head == null){
                       last = null;
                   }else{
                       head.prev = null;
                   }
                }else if(tem.next == null){
                    last = last.prev;
                    if(last == null){
                        head = null;
                    }else {
                        tem.prev.next = null;
                    }
                }else{
                    tem.next.prev = tem.prev;
                    tem.prev.next = tem.next;
                }

                this.count--;
                return;
            }
            tem = tem.next;
        }
    }

    //移除全部指定元素
    public void removeAll(int key){

        ListNode tem = head;

        while(tem != null){
            if(tem.val == key){
                if(tem == head){
                    head = head.next;
                    if(head == null){
                        last = null;
                    }else{
                        head.prev = null;
                    }
                }else if(tem.next == null){
                    last = last.prev;
                    if(last == null){
                        head = null;
                    }else {
                        tem.prev.next = null;
                    }
                }else{
                    tem.next.prev = tem.prev;
                    tem.prev.next = tem.next;
                }

                this.count--;
            }
            tem = tem.next;
        }
    }

    public void clear(){
       ListNode cur = head;

       while(cur != null){
           ListNode curN = cur.next;
           cur.prev = null;
           cur.next = null;

           cur = curN;

       }
       head = null;
       last = null;
    }

    public void display() {

        ListNode tem = head;
        System.out.print("[ ");
        while(tem != null){
            System.out.print(tem.val + " ");
            tem = tem.next;
        }
        System.out.println("]");

    }
}
